#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @FileName  :clone-graph.py
# @Time      :2024/1/26 7:51
# @Author    :chitandacc@126.com


"""https://leetcode.cn/problems/clone-graph/description/"""

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

from collections import deque

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

from typing import Optional

temp_list = list()
result = dict()
node_list = []

from collections import deque


class Solution:
    def cloneGraph1(self, node: Optional['Node']) -> Optional['Node']:
        # 第二次刷，完全不理解题目再说些啥  代码也不知道怎么写成这样子了，真离谱 error
        if not result.__contains__(node.val):
            result[node.val] = [i.val for i in node.neighbors]
            for next_node in node.neighbors:
                if not result.__contains__(next_node.val):
                    temp_list.append(next_node)
        if temp_list:
            next_no = temp_list.pop()
            return self.cloneGraph(next_no)
        return list(result.values())

    def cloneGraph(self, node):
        if node is None:
            return node
        visted = dict()
        queue = deque([node])
        node2 = Node(node.val)
        queue2 = deque([node2])
        visted[node] = node2
        while queue:
            nod = queue.popleft()
            newNode = queue2.popleft()
            for next_node in nod.neighbors:
                if next_node in visted:
                    newNode.neighbors.append(visted[next_node])
                else:
                    next_node2 = Node(next_node.val)
                    queue.append(next_node)
                    queue2.append(next_node2)
                    visted[next_node] = next_node2
                    newNode.neighbors.append(next_node2)
        return visted[node]

    def cloneGraph3(self, node):
        check = defaultdict(int)

        def dfsNode(node):
            if node is None:
                return None
            newNode = Node(node.val)
            check[newNode.val] = newNode
            for nod in node.neighbors:
                if check[nod.val] != 0:
                    newNode.neighbors.append(check[nod.val])
                else:
                    tempNode = dfsNode(nod)
                    if tempNode is not None:
                        newNode.neighbors.append(tempNode)
            return newNode

        if node is None:
            return
        res = dfsNode(node)
        return res

